package acwing._1_1AlgorithmBasic;
/**
 * @Project : AlgorithmLearning
 * @Package : ACWing._1_1AlgorithmBasic._3SearchGraph
 * @File : _3_2TreeGraph.java
 * @Author : WangRuoyu
 * @Date : 2023/4/2 8:54
 */

import java.util.LinkedList;
import java.util.Queue;
import java.util.ArrayList;

public class _3_2TreeGraph {
    static final int N = 1000010;
    static int n;
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] next = new int[N];
    static boolean[] st = new boolean[N];
    static int idx = 0;

    // Arrays.fill(h,-1);

    static void add(int a, int b) {
        e[idx] = b;
        next[idx] = h[a];
        h[a] = idx++;
    }

    // 图与树的深搜
    static void dfs(int u) {
        st[u] = true;
        for (int i = h[u]; i != -1; i = next[i]) {
            int j = e[i];
            if (!st[j]) dfs(j);
        }
    }

    // 图与树的宽搜
    static int bfs() {
        int res = -1;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{1, 0});
        st[1] = true;
        while (!q.isEmpty()) {
            int[] point = q.poll();
            if (point[0] == n) {
                res = point[1];
                break;
            }
            for (int i = h[point[0]]; i != -1; i = next[i]) {
                int j = e[i];
                if (!st[j]) {
                    st[j] = true;
                    q.add(new int[]{j, point[1] + 1});
                }
            }
        }
        return res;
    }

    // 拓扑排序
    static int[] degree; // 记录入度
    static boolean topsort(ArrayList<Integer> res) {
        Queue<Integer> q = new LinkedList<>();

        for (int i = 1; i <= n; ++i) {
            if (degree[i] == 0) {
                q.add(i);
                degree[i] = -1;
            }
        }

        while (!q.isEmpty()) {
            int p = q.poll();
            res.add(p);
            for (int i = h[p]; i != -1; i = next[i]) {
                int j = e[i];
                degree[j]--;
                if (degree[j] == 0) {
                    q.add(j);
                    degree[j] = -1;
                }
            }
        }

        return res.size() == n;
    }
}



